Хроматический полином
Лемма. Хроматический полином графа имеет вид
P(G,x) = P(G1,x) +P(G2,x), |
|
где
G1 - граф, полученный из G добавлением нового ребра (uv), а граф G2 получается из
G отождествлением вершин u и v.
Задача. Найти хроматический полином графа
Решение
Способ 1
Воспользуемся леммой, записанной в виде
P(G1,x) = P(G,x) - P(G2,x) |
|
Убирая ребра и отождествляя соответствующие вершины,
сведем исходный граф к пустым графам. Известно, что для пустого графа P(On,x)=xn.
G = G1- G2 = O4- O3 - 2(O3 - O2)-(O3- O2 - 2(O2 - O1))=O4- 4O3 + 5O2 - 2O1. |
|
Способ 2. Хроматическая редукция
Добавляя ребра и отождествляя соответствующие вершины, получим полные графы.
Известно, что для полного графа хроматический полином равен факториальной степени
переменной P(On,x)=x(n).
P(G,x) = x(4)+2x(3) = x(x-1)(x-2)(x-3) + 2 x(x-1)(x-2) = x4-4x3+5x2-2x |
|
Заметим, что
где s1(n,k) - числа Стирлинга первого рода.
где s2(n,k) - числа Стирлинга второго рода, обладающие следующими свойствами
s2(n,k) = s2(n-1,k-1)+ks2(n-1,k), 0 < k < n, |
|
|